package com.hot100.mid;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.function.Function;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 链表排序
 * @date 2022/9/3 15:19
 */
public class Demo34 {
    public ListNode sortList(ListNode head) {
        return getListNode1(head);

    }

    //归并排序
    private ListNode getListNode1(ListNode head) {
        //退出条件
        if (head == null || head.next == null) {
            return head;
        }
        //快慢指针找到中间点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = head.next.next;
        }
        //slow即为中心点
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left = getListNode1(head);
        ListNode right = getListNode1(temp);
        //归并排序left和right
        ListNode newNode = new ListNode(-1);
        ListNode pre = newNode;
        while (left != null && right != null) {
            if (left.val > right.val) {
                pre.next = new ListNode(right.val);
                right = right.next;
            } else {
                pre.next = new ListNode(left.val);
                left = left.next;
            }
            pre = pre.next;
        }
        while (left != null) {
            pre.next = new ListNode(left.val);
            left = left.next;
            pre = pre.next;
        }
        while (right != null) {
            pre.next = new ListNode(right.val);
            right = right.next;
            pre = pre.next;
        }
        return newNode.next;
    }

    //面试不会给通过的
    private ListNode getListNode(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        ListNode listNode = new ListNode(-1);
        ListNode pre = listNode;
        Collections.sort(list);
        for (int i = list.size() - 1; i >= 0; i--) {
            pre.next = new ListNode(list.get(i));
            pre = pre.next;
        }
        return listNode.next;
    }

    /**
     * Definition for singly-linked list.
     */
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
